public class Sort {
    //插入排序
    public static void insertSort(int[] array){
        int tmp = 0;
        for(int i = 1;i < array.length; i++){
            tmp = array[i];
            int j = i -1;
            for (; j >= 0 ; j--) {
                if(tmp < array[j]){
                    array[j +1] =array[j];//将前面的数向后移 给插入的数空出位置

                }else{
                    //array[j +1] = tmp;//进行插入（因为结束循环要执行一次，防止插入2次）
                    break;
                }
            }
            array[j +1] = tmp;//进行插入
        }

    }


    //========================================================================//

    //希尔排序（基于插入排序，只不过进行了分组）
    public static void shellSort(int []array){
        int gap = array.length;
        while (gap > 1){
            gap /= 2;
            shell(array,gap);
        }
    }

    public static void shell(int[] array,int gap){

        int tmp = 0;
        for(int i = gap;i < array.length; i ++){
            tmp = array[i];
            int j = i -gap;
            for (; j >= 0 ; j-= gap) {
                if(tmp < array[j]){
                    array[j +gap] =array[j];

                }else{
                    //array[j +1] = tmp;//进行插入（因为结束循环要执行一次，防止插入2次）
                    break;
                }
            }
            array[j + gap] = tmp;//进行插入
        }
    }

    //==========================================================//
    //选择排序
    public static void selectSort(int []array){

        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if(array[j] < array[minIndex]){  //有比它小的 就交换下标
                    minIndex = j;
                }
            }
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }

    //========================================================//
    //冒泡排序
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length -1; i++) {//控制趟数

            boolean flag = false;

            for (int j = 0; j < array.length - 1 -i; j++) {//控制次数
                if(array[j] > array[j + 1]){
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag = true;
                }
            }

            if(!flag){//如果没有交换，说明排序好了
                return;
            }
        }
    }

    //========================================================//
    //快速排序
    public static void quickSort(int []array){
        quick(array,0, array.length - 1 );
    }

    private static void quick(int[] array,int start,int end) {//用到了二叉树的递归思想
        if(start >= end){//左边一个节点 或者 一个节点都没有
            return;
        }

        //三数取中（优化递归） 使树把中间的值作为根节点，降低树的高度
        int mid =  midOfThree(array,start,end);

        swap(array,mid,start);//保证start下标一定是中间大的数字
        int pivot = parttion(array,start,end);

        quick(array,start,pivot -1);//递归遍历左边
        quick(array,pivot + 1,end);//递归遍历右边
    }

    private static int  midOfThree(int[] array, int start, int end) { //取三个数的中间值
        int mid = (start + end) /2;
        if(array[start] > array[end]){

            if(array[mid] > array[start]){
                return start;
            }else if(array[mid] < array[end]){
                return end;
            }else {
                return mid;
            }
        }else {

            if(array[mid] < array[start]){
                return start;
            }else if(array[mid] > array[end]){
                return end;
            }else {
                return mid;
            }
        }
    }

    private static int parttion(int[] array, int start, int end) {//找到基准（也就是根节点）

        int i = start;
        int key = array[start];

        //int pivot = array[left](挖坑法)
        while (start < end){
            while (start < end && array[end] >= key){
                end--;
            }//此时的end下标的值一定是比pivot下标的值小

            //array[right] = array[left]
            while (start < end && array[start] <= key){
                start ++;
            }//同理

            //array[left] = array[right]
            swap(array,start,end);
        }
        //array[left] = pivot
        swap(array,i, start);//此时相遇
        return start;

    }

    public static void swap(int[] array,int i , int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //挖坑法（和快排类似）


    //===============================================================//
    //归并排序
    public static void mergeSort(int[] array){
        mergeSortFunc(array,0,array.length - 1);
    }

    private static void mergeSortFunc(int[] array, int left, int right) {
        if(left >= right){
            return;
        }

        //分开
        int mid = (left + right)/ 2;

        mergeSortFunc(array,left,mid);//左边遍历
        mergeSortFunc(array,mid + 1,right);//右边遍历

        //合并
        merge(array,left,mid,right);

    }

    private static void merge(int[] array,int left,int mid ,int right){
        int s1 = left;
        int s2 = mid + 1;

        int[] tmpArr = new int[right - left +1];
        int k = 0;

        while (s1 <= mid && s2 <= right){
            if(array[s1] < array[s2]){
                tmpArr[k++] = array[s1++];

            }else {
                tmpArr[k++] = array[s2++];

            }
        }

        //防止有一个数组全部放入 另一个还有数据
        while (s1 <= mid){
            tmpArr[k++] = array[s1++];
        }

        while (s2 <= right){
            tmpArr[k++] = array[s2++];
        }

        //tmpArr中的数据一定是这个区间的有序数据
        for (int i = 0; i < tmpArr.length; i++) {
            array[i + left] = tmpArr[i];
        }
    }
    //=========================================================================//
    //计数排序
    public static void countSort(int[] array){
        int maxVal = array[0];
        int minVal = array[0];

        //找出数组中最大值最小值
        for (int i = 0; i < array.length - 1; i++) {
            if(array[i] > maxVal){
                maxVal = array[i];
            }

            if(array[i] < minVal){
                minVal = array[i];
            }
        }

        //根据最大值最小值 确定数组大小
        int[] count = new int[maxVal - minVal];

        //开始计数
        for (int i = 0; i < array.length; i++) {
            count[array[i] - minVal] ++;        //优化用[array[i] - minVal就是得到 个位上的数
        }

        //根据count 将数据写回 原数组
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0){
                array[index] = i + minVal;//真实的数据的值
                count[i] --;
                index ++;
            }
        }
    }
}
